\section{Future Work and Conclusions}\label{sec:conc}

We have presented efficient decentralized algorithms for finding dense subgraphs in distributed dynamic networks. Our algorithms not only show how to compute size-constrained dense subgraphs with provable approximation guarantees, but also show how these can be {\em maintained} over time. While there has been significant research on several variants of the dense subgraph computation problem in the classical setting, to the best of our knowledge this is the first formal treatment of this problem for a distributed peer-to-peer network model.

Several directions for future research result naturally out of our work. The first specific question is whether our algorithms and analyses can be improved to guarantee $O(D + \log n)$ rounds instead of $O(D\log n)$, even in static networks. Alternatively, can one show a lower bound of $\Omega(D\log n)$ in static networks? Bounding the value $D$ in terms of the instantaneous graphs and change rate $r$ would also be an interesting direction of future work.
It is also interesting to show whether the densest subgraph problem can be solved {\em exactly} in $O(D\poly\log n)$ or not in the static setting, and to develop dynamic algorithms without density lower bound assumptions. Another open problem (suggested to us by David Peleg) that seems to be much harder is the {\em at-most-$k$ densest subgraph problem}.
%
One could also consider various other definitions of density and study distributed algorithms for them, as well as explore whether any of these techniques extend directly or indirectly to specific applications. Finally, it would be interesting to extend our results from the edge alteration model to allow node alterations as well.
